// 插值查找 针对有序数组 mid= low  + (high - low) * (key - a[low]) / (a[high] - a[low])
/**
 *
 * @param arr {Array} 数组 升序
 * @param left {number} 左边索引
 * @param right {number} 右边索引
 * @param findVal {number} 要查找的值
 */
function insertValueSearch (arr, left, right, findVal) {
    // 当left>right时 说明递归了整个数组 没有找到
    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
        return -1
    }
    let mid = ~~(left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]))
    let midVal = arr[mid]
    if (findVal > midVal) { //向右递归
        return insertValueSearch(arr, mid + 1, right, findVal)
    } else if (findVal < midVal) { // 向左递归
        return insertValueSearch(arr, left, mid - 1, findVal)
    } else {
        return mid
    }
}

function main () {
    let arr = []
    for (let i = 0; i < 100; i++) {
        arr.push(i)
    }
    let index = insertValueSearch(arr, 0, arr.length - 1, 0)
    console.log(index)
}

main()
